package question.base;

/**
 * @author: 26233
 * @create: 2021-12-22 22:44:53
 * @Description
 *
 * 汉诺塔问题：
 * 有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘
 * 现要求将A柱子上的圆盘移到C柱子上去
 * 期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
 *
 * 1. 将s上的所有移动到d上，t为第三个柱子
 * 2. (s -> d)M({1,2,3...n}) = (s -> t)M({1,2,3...(n-1)}) => (s, d)M({n}) => (t -> d)M({1,2,3...(n-1)}) 按序执行最基本的三个过程
 *  (s -> d)M({1,2,3...n}) 表示将1..n从s移动到d
 *  (s -> t)M({1,2,3...(n - 1)}) 表示将1..(n-1)从s移动到t
 *  (s, d)M({n}) 表示将n从s移动到d
 *  (t -> d)M({1,2,3...(n - 1)}) 表示将1..(n-1)从t移动到d
 *
 * 3. 一定次数2^n - 1
 **/

public class HannuoTower {

    int moveTime;

    public void hannuoTower(int high, char s, char d, char t){

        if(high == 1){
            System.out.printf("move %d from %c -> %c\n", high, s, d);
            moveTime++;
        }else {
            hannuoTower(high - 1, s, t, d);
            System.out.printf("move %d from %c -> %c\n", high, s, d);
            moveTime++;
            hannuoTower(high - 1, t, d, s);
        }

    }

    public static void main(String[] args) {
        HannuoTower hannuoTower = new HannuoTower();
        hannuoTower.hannuoTower(15, 'S', 'D', 'T');
        System.out.println("hannuoTower.moveTime = " + hannuoTower.moveTime);
    }

}
